package main

import "fmt"

/*
无重复字符串的排列组合/字符串的排列

无重复字符串的排列组合。编写一种方法，计算某字符串的所有排列组合，字符串每个字符均不相同。
示例1:
 输入：S = "qwe"
 输出：["qwe", "qew", "wqe", "weq", "ewq", "eqw"]

示例2:
 输入：S = "ab"
 输出：["ab", "ba"]
*/
func permutation(S string) []string {
	n := len(S)
	var ans []string
	var path []byte
	visit := make([]bool, n)
	var dfs func(idx int)
	dfs = func(idx int) {
		if idx == n {
			ans = append(ans, string(path))
		}
		for i := 0; i < n; i++ {
			if !visit[i] {
				path = append(path, S[i])
				visit[i] = true
				dfs(idx + 1)
				visit[i] = false
				path = path[:len(path)-1]
			}
		}
	}
	dfs(0)
	return ans
}

func main() {
	S := "qwe"
	fmt.Println(permutation(S))
}
